#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
    // 使用数组+散列表实现数组操作O(1)复杂度
public:
    Solution() {}
    
    bool insert(int val) {
        // 已存在，返回false，插入成功，返回true
        if (valToIndex.count(val))
            return false;
        valToIndex[val] = nums.size();
        nums.push_back(val);
        return true;
    }

    bool remove(int val) {
        // 不存在，返回false，删除成功，返回true
        if (!valToIndex.count(val))
            return false;
        // 获取待删除元素的索引
        int index = valToIndex[val];
        // 将nums末尾元素索引设为index
        valToIndex[nums.back()] = index;
        // 将待删除元素换到nums末尾
        swap(nums[index], nums.back());
        // 删除末尾元素
        nums.pop_back();
        // 清除val的索引
        valToIndex.erase(val);
    
        return true;
    }

    int getRandomValue() {
        return nums[rand() % nums.size()];
    }

private:
    vector<int> nums;
    unordered_map<int, int> valToIndex;
};

class randomExceptBlackList {
public:
    randomExceptBlackList(int N, vector<int>& blacklist) {
        tail = N - blacklist.size();
        for (vector<int>::iterator iter = blacklist.begin(); iter != blacklist.end(); iter++)
            mapping[*iter] = -1;        // 标记黑名单元素，以便下一步操作
        int last = N - 1;           // 映射起点
        for (vector<int>::iterator iter = blacklist.begin(); iter != blacklist.end(); iter++) {
            if (*iter >= tail)      // 黑名单元素位于数组尾部，不需要移动
                continue;
            while (mapping.count(last))
                last--;             // 映射起点已经被使用，所以将映射起点前移
            mapping[*iter] = last;  // 映射黑名单元素到可用的映射起点，！！就像是将黑名单元素与非黑名单元素互换了
            last--;                 // 映射起点前移
        }
    }

    int pick() {
        int index = rand() % tail;  // 获取随机的index
        if (mapping.count(index))
            return mapping[index];  // 如果是黑名单元素，则去获取其映射到的非黑名单元素
        return index;               // 不是黑名单元素，则直接返回
    }
private:
    int tail;   // 标记删除黑名单后的数组尾部位置
    unordered_map<int, int> mapping;    // 将黑名单元素映射到数组末尾
};